The maximum common connected edge subgraph problem is to find a connected\r\ngraph with the maximum number of edges that is isomorphic to a subgraph of each of the\r\ntwo input graphs, where it has applications in pattern recognition and chemistry. This paper\r\npresents a dynamic programming algorithm for the problem when the two input graphs\r\nare outerplanar graphs of a bounded vertex degree, where it is known that the problem is\r\nNP-hard, even for outerplanar graphs of an unbounded degree. Although the algorithm\r\nrepeatedly modifies input graphs, it is shown that the number of relevant subproblems is\r\npolynomially bounded, and thus, the algorithm works in polynomial time.
Loading....